Namespacing everything to /UVa.
[andmenj-acm.git] / UVa / 11466 - Largest prime divisor / 11466.cpp
blob6a5cf5e68bd2c477a89eb5c4be46ffdcbaa3286c
1 #include <iostream>
2 #include <map>
3 #include <cassert>
4 #include <algorithm>
5 #include <cmath>
7 using namespace std;
9 typedef unsigned long long ull;
10 typedef long long ll;
12 map<ull, long long> cache;
14 void f(ull x)
16 ull i; /* counter */
17 ull c; /* remaining product to factor */
18 ll r = cache[x];
19 if (r == 0){
20 c = x;
21 while ((c % 2) == 0) {
22 //printf("2\n");
23 c = c / 2;
24 r = 2;
26 i = 3;
27 ull raiz = sqrt(c)+1;
28 while (i <= raiz) {
29 if ((c % i) == 0) {
30 //printf("i: %lld\n", i);
31 c = c / i;
32 raiz = (sqrt(c)+1);
33 r = i;
35 else
36 i = i + 2;
38 if (c > r){
39 r = c;
40 //printf("c: %lld\n", c);
42 //printf("c quedo en: %lld\n", c);
43 //printf("r quedo en: %lld\n", r);
45 c = r;
46 while (c <= x){
47 if (c == x){
48 r = -1;
49 break;
51 c *= r;
53 cache[x] = r;
55 printf("%lld\n", r);
56 //assert(r < x);
60 int main(){
61 long long n;
62 while (scanf("%lld", &n) == 1 && n){
63 if (n < 0) n *= -1;
64 //assert(n > 0);
65 f(n);
67 return 0;